#define _CRT_SECURE_NO_WARNINGS 1


#include<vector>
#include<iostream>

using namespace std;

class Solution
{
public:
    void _MergeSort(vector<int>& v, int left, int right, vector<int>& temp)
    {
        if (left >= right)
        {
            return;
        }
        int mid = left + (right - left) / 2;
        _MergeSort(v, left, mid, temp);
        _MergeSort(v, mid + 1, right, temp);
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = left;
        while (begin1 <= end1 && begin2 <= end2)
        {
            if (v[begin1] < v[begin2])
            {
                temp[index++] = v[begin1++];
            }
            else
            {
                temp[index++] = v[begin2++];
            }
        }
        while (begin1 <= end1)
        {
            temp[index++] = v[begin1++];
        }
        while (begin2 <= end2)
        {
            temp[index++] = v[begin2++];
        }
        for (int i = left; i <= right; i++)
        {
            v[i] = temp[i];
        }
    }

    void MergeSort(vector<int>& v, int n)
    {
        vector<int> temp(n);
        _MergeSort(v, 0, n - 1, temp);
    }

    vector<int> sortArray(vector<int>& nums)
    {
        MergeSort(nums, nums.size());
        return nums;
    }
};